/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sort-integers-ii
   @Language: C++
   @Datetime: 16-12-07 09:47
   */

class Solution {
	//////////// quick sort begin /////////////
	void quick_sort(vector<int>& A, int begin, int end)
	{
		int i=begin, j=end-1, key;
		if (i>=j) return;
		for(key=A[i]; i<j;){
			for(; i<j && A[j]>=key; --j);
			A[i] = A[j];
			for(; i<j && A[i]<=key; ++i);
			A[j] = A[i];
		}
		A[i] = key;
		quick_sort(A,begin,i);
		quick_sort(A,i+1,end);
	}	/////////// quick sort end //////////

	/////////////// heap sort begin /////////////
	void heap_adjust(vector<int>& A, int p, int n)
	{	// c - children, p - parent
		// heap_adjust for maxtop, from top to bottom
		for(int maxid=p; p<(n>>1); p=maxid){
			if ((p<<1)+1<n && A[(p<<1)+1]>A[maxid])
				maxid = (p<<1)+1;
			if ((p<<1)+2<n && A[(p<<1)+2]>A[maxid])
				maxid = (p<<1)+2;
			if (maxid == p) break;
			swap(A[maxid],A[p]);
		}
	}
	void heap_sort(vector<int> &A, int n){
		// init maxtop heap, from bottom to top
		for (int i=(n>>1)-1; i>-1; heap_adjust(A,i--,n));
		for (int i=n-1; i>0; --i){
			// mv heap top to end (heap top is max)
			swap(A[0],A[i]);
			heap_adjust(A,0,i);
		}
	}	///////////// heap sort end ////////////

	///////////////// merge sort begin /////////////
	void merge_core(vector<int> &A, int begin, int mid, int end){
		int i, j, k = end-begin;
		vector<int> tmp(k,0);
		for(i=mid, j=end; i!=begin && j!=mid;)
			tmp[--k] = (A[i-1]>A[j-1] ? A[--i]:A[--j]);
		for(; i!=begin; tmp[--k]=A[--i]);
		for(; j!=mid; tmp[--k]=A[--j]);
		// copy to A
		for(i=begin, k=0; i<end; A[i++]=tmp[k++]);
	}
	void merge_sort(vector<int> &A, int begin, int end){
		if (end-begin<2) return;
		int mid = (begin+end)>>1;
		merge_sort(A,begin,mid);
		merge_sort(A,mid,end);
		merge_core(A,begin,mid,end);
	}	////////////// merge sort end ////////////

public:
	/**
	 * @param A an integer Aay
	 * @return void
	 */
	/**
	 * There are 3 methods, visit notes for details
	 *
	 * */
	void sortIntegers2(vector<int>& A) {
		// Method 1 : quick sort, Time O(nlogn), Space O(1)
		quick_sort(A,0,A.size());

		// Method 2 : heap sort , Time O(nlogn), Space O(1)
		heap_sort(A,A.size());

		// Method 3 : merge sort, Time O(nlogn), Space O(n)
		merge_sort(A,0,A.size());
	}
};

